home *** CD-ROM | disk | FTP | other *** search
/ CU Amiga Super CD-ROM 18 / CU Amiga Magazine's Super CD-ROM 18 (1997)(EMAP Images)(GB)[!][issue 1998-01].iso / CUCD / Online / hsc / source / ugly / dllist.c < prev    next >
Encoding:
C/C++ Source or Header  |  1997-11-02  |  9.8 KB  |  438 lines
  1. /*
  2.  * This source code is part of hsc, a html-preprocessor,
  3.  * Copyright (C) 1993-1997  Thomas Aglassinger
  4.  *
  5.  * This program is free software; you can redistribute it and/or modify
  6.  * it under the terms of the GNU General Public License as published by
  7.  * the Free Software Foundation; either version 2 of the License, or
  8.  * (at your option) any later version.
  9.  *
  10.  * This program is distributed in the hope that it will be useful,
  11.  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  12.  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  13.  * GNU General Public License for more details.
  14.  *
  15.  * You should have received a copy of the GNU General Public License
  16.  * along with this program; if not, write to the Free Software
  17.  * Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
  18.  *
  19.  */
  20. /*
  21.  * ugly/dllist.c
  22.  *
  23.  * double linked list processing functions
  24.  *
  25.  * Copyright (C) 1994,95,96  Thomas Aglassinger
  26.  *
  27.  * This program is free software; you can redistribute it and/or modify
  28.  * it under the terms of the GNU General Public License as published by
  29.  * the Free Software Foundation; either version 2 of the License, or
  30.  * (at your option) any later version.
  31.  *
  32.  * This program is distributed in the hope that it will be useful,
  33.  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  34.  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  35.  * GNU General Public License for more details.
  36.  *
  37.  * You should have received a copy of the GNU General Public License
  38.  * along with this program; if not, write to the Free Software
  39.  * Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
  40.  *
  41.  * updated:  9-Mar-1997
  42.  * created:  1-Mar-1994
  43.  *
  44.  *---------------------------------------------------------
  45.  */
  46.  
  47. #include <stdlib.h>
  48. #include <stdio.h>
  49.  
  50. #include "utypes.h"
  51. #include "umemory.h"
  52.  
  53. /* include header file without external prototypes */
  54. #define NOEXTERN_UGLY_DLLIST_H
  55. #include "dllist.h"
  56.  
  57. /*
  58.  * init_dllist
  59.  *
  60.  * alloc & initialise new double linked list
  61.  *
  62.  * result: ptr to new list
  63.  * errors: return NULL (out of mem)
  64.  *
  65.  */
  66. DLLIST *init_dllist(void (*fn_del_data) (APTR data))
  67. {
  68.     DLLIST *newlist;
  69.  
  70.     newlist =                   /* alloc mem for list */
  71.         umalloc(sizeof(DLLIST));
  72.  
  73.     if (newlist)
  74.     {
  75.         newlist->first = NULL;  /* init new list */
  76.         newlist->last = NULL;
  77.         newlist->entry_num = 0;
  78.         newlist->user_data = NULL;
  79.         newlist->del_data = fn_del_data;
  80.     }
  81.  
  82.     return newlist;             /* return new list */
  83. }
  84.  
  85. /*
  86.  * new_dlnode()
  87.  *
  88.  * alloc & init new double linked list node
  89.  *
  90.  * result: new list node
  91.  * errors: return NULL (out of mem)
  92.  *
  93.  */
  94. DLNODE *new_dlnode(void)
  95. {
  96.     DLNODE *newnode;
  97.  
  98.     newnode =                   /* alloc mem for new node */
  99.         umalloc(sizeof(DLNODE));
  100.  
  101.     if (newnode)
  102.     {                           /* alloc successful? */
  103.         newnode->prev = NULL;   /* Y-> init node */
  104.         newnode->next = NULL;
  105.         newnode->data = NULL;
  106.     }
  107.  
  108.     return newnode;             /* return newnode */
  109. }
  110.  
  111. /* 
  112.  * detach_dlnode()
  113.  *
  114.  * remove entry from double linked list,
  115.  * but do not delete the entries data
  116.  *
  117.  */
  118. APTR detach_dlnode(DLLIST * list, DLNODE * node)
  119. {
  120.     APTR nd_data = NULL;
  121.  
  122.     if (list && node)
  123.     {                           /* list & node node defined? */
  124.         nd_data = node->data;   /*     remeber data */
  125.         if (node->prev)         /*     remove node from list */
  126.             node->prev->next = node->next;
  127.         else
  128.             list->first = node->next;
  129.         list->entry_num--;
  130.  
  131.         if (node->next)
  132.             node->next->prev = node->prev;
  133.         else
  134.             list->last = node->prev;
  135.  
  136.         ufree(node);            /*     free node */
  137.     }
  138.  
  139.     return nd_data;
  140. }
  141.  
  142. /* 
  143.  * del_dlnode()
  144.  *
  145.  * remove entry from double linked list
  146.  *
  147.  */
  148. void del_dlnode(DLLIST * list, DLNODE * node)
  149. {
  150.  
  151.     if (list && node)
  152.     {                           /* list & node node defined? */
  153.         void (*dd) (APTR) = list->del_data;
  154.  
  155.         if (node->data)         /* Y-> call destructor */
  156.             if (dd)
  157.                 (*dd) (node->data);
  158.  
  159.         if (node->prev)         /*     remove node from list */
  160.             node->prev->next = node->next;
  161.         else
  162.             list->first = node->next;
  163.         list->entry_num--;
  164.  
  165.         if (node->next)
  166.             node->next->prev = node->prev;
  167.         else
  168.             list->last = node->prev;
  169.  
  170.         node->prev = NULL;      /*     clear node */
  171.         node->next = NULL;
  172.         node->data = NULL;
  173.  
  174.         ufree(node);            /*     free node */
  175.     }
  176. }
  177.  
  178. /*
  179.  * del_all_dlnodes()
  180.  *
  181.  * remove all nodes from a list
  182.  */
  183. VOID del_all_dlnodes(DLLIST * list)
  184. {
  185.     while (list->first)
  186.         del_dlnode(list, list->first);
  187. }
  188.  
  189. /*
  190.  * ins_dlnode()
  191.  *
  192.  * insert a data entry into double linked list BEFORE node
  193.  *
  194.  */
  195. DLNODE *ins_dlnode(DLLIST * list, DLNODE * node, APTR data)
  196. {
  197.     DLNODE *newnode = NULL;
  198.  
  199.     if (list)
  200.     {
  201.         newnode = new_dlnode();
  202.  
  203.         if (newnode)
  204.         {
  205.             newnode->data = data;
  206.             list->entry_num++;
  207.  
  208.             if (node)
  209.             {
  210.                 if (list->first == node)
  211.                 {
  212.                     /*
  213.                      * insert as first entry
  214.                      */
  215.                     list->first = newnode;
  216.                 }
  217.                 else
  218.                 {
  219.                     /*
  220.                      * insert somewhere in the list
  221.                      */
  222.                     node->prev->next = newnode;
  223.                     newnode->prev = node->prev;
  224.                 }
  225.                 node->prev = newnode;
  226.                 newnode->next = node;
  227.             }
  228.             else
  229.             {                   /* append as last entry */
  230.                 if (list->last)
  231.                     list->last->next = newnode;
  232.                 newnode->prev = list->last;
  233.                 list->last = newnode;
  234.             }
  235.  
  236.             if (list->first == NULL)
  237.                 list->first = newnode;
  238.             if (list->last == NULL)
  239.                 list->last = newnode;
  240.         }
  241.     }
  242.  
  243.     return newnode;
  244. }
  245.  
  246. /*
  247.  * app_dlnode
  248.  *
  249.  * append new node to list (at end)
  250.  *
  251.  * result:
  252.  * errors: return NULL (out of mem)
  253.  *
  254.  */
  255. DLNODE *app_dlnode(DLLIST * list, APTR data)
  256. {
  257.     DLNODE *newnode = NULL;
  258.  
  259.     if (list)
  260.     {
  261.         newnode = ins_dlnode(list, NULL, data);
  262.     }
  263.  
  264.     return newnode;
  265. }
  266.  
  267. /*
  268.  * add_dlnode
  269.  *
  270.  * add new node to list (as first entry)
  271.  *
  272.  * result: new node
  273.  * errors: return NULL (out of mem)
  274.  *
  275.  */
  276. DLNODE *add_dlnode(DLLIST * list, APTR data)
  277. {
  278.     DLNODE *newnode = NULL;
  279.  
  280.     if (list)
  281.     {
  282.         newnode = ins_dlnode(list, list->first, data);
  283.     }
  284.  
  285.     return newnode;
  286. }
  287.  
  288. /*
  289.  * del_dllist
  290.  *
  291.  * free whole list and its nodes and data
  292.  *
  293.  */
  294. void del_dllist(DLLIST * list)
  295. {
  296.     if (list)
  297.     {
  298.         /* remove all nodes */
  299.         while (list->first)
  300.             del_dlnode(list, list->first);
  301.  
  302.         /* remove list structure */
  303.         list->first = NULL;
  304.         list->last = NULL;
  305.         list->entry_num = 0;
  306.         list->user_data = NULL;
  307.         list->del_data = NULL;
  308.         ufree(list);
  309.     }
  310. }
  311.  
  312. /*
  313.  * do_dllist
  314.  *
  315.  * call a function with every node of a list
  316.  */
  317. void do_dllist(DLLIST * list, void (*func) (APTR data))
  318. {
  319.     if (list)
  320.     {
  321.         DLNODE *nd = list->first;
  322.  
  323.         while (nd)
  324.         {
  325.             (*func) (nd->data);
  326.             nd = nd->next;
  327.         }
  328.     }
  329. }
  330.  
  331. /*
  332.  * fprintf_dllist
  333.  *
  334.  * output a whole list to a stream
  335.  * (more or less only a debugging function)
  336.  */
  337. void fprintf_dllist(FILE * stream, DLLIST * list,
  338.                     void (*fprintf_data) (FILE * stream, APTR data))
  339. {
  340.     if (list)
  341.     {
  342.         DLNODE *node;
  343.         ULONG i = 1;
  344.  
  345.         node = list->first;
  346.         if (node)
  347.         {
  348.             while (node)
  349.             {
  350.                 fprintf(stream, "%4lu: ", i++);
  351.                 if (fprintf_data)
  352.                     (*fprintf_data) (stream, node->data);
  353.                 else
  354.                     fprintf(stream, "%s\n", (STRPTR) node->data);
  355.                 node = node->next;
  356.             }
  357.         }
  358.         else
  359.             fprintf(stream, "  [empty list]\n");
  360.     }
  361.     else
  362.         fprintf(stream, "  [no list]\n");
  363. }
  364.  
  365. /*
  366.  * find_dlnode
  367.  *
  368.  * search for specific data in a list, starting at a specific node
  369.  *
  370.  * params: start....startnode to begin search with
  371.  *         data.....data to be found
  372.  *         compare..funtions that compares two data-items;
  373.  *                  returns -1 if items are equal, else 0
  374.  * result: ptr to node that contains requested data
  375.  *         or NULL if not found
  376.  */
  377. DLNODE *find_dlnode(DLNODE * start, APTR data,
  378.                     int (*compare) (APTR cmp_data, APTR list_data))
  379. {
  380.     DLNODE *search = start;
  381.     int found = 0;
  382.  
  383.     while (search && !(found))
  384.     {
  385.         found = (*compare) (data, search->data);
  386.         if (!found)
  387.             search = search->next;
  388.     }
  389.  
  390.     return search;
  391. }
  392.  
  393. /*
  394.  * find_dlnode_bw
  395.  *
  396.  * search for specific data in a list, starting at a specific node,
  397.  * search directions set to backwards
  398.  *
  399.  * params: start....startnode to begin search with
  400.  *         data.....data to be found
  401.  *         compare..funtions that compares two data-items;
  402.  *                  returns -1 if items are equal, else 0
  403.  * result: ptr to node that contains requested data
  404.  *         or NULL if not found
  405.  */
  406. DLNODE *find_dlnode_bw(DLNODE * start, APTR data,
  407.                     int (*compare) (APTR cmp_data, APTR list_data))
  408. {
  409.     DLNODE *search = start;
  410.     int found = 0;
  411.  
  412.     while (search && !(found))
  413.     {
  414.         found = (*compare) (data, search->data);
  415.         if (!found)
  416.             search = search->prev;
  417.     }
  418.  
  419.     return search;
  420. }
  421.  
  422. /*
  423.  * empty_dllist
  424.  *
  425.  * check if a list is empty
  426.  *
  427.  * params: list..list to check for emptyness
  428.  * result: TRUE, if list contains no nodes
  429.  */
  430. BOOL empty_dllist(DLLIST * list)
  431. {
  432.     if (list->first)
  433.         return TRUE;
  434.     else
  435.         return FALSE;
  436. }
  437.  
  438.